package code.class5;

/**
 * https://leetcode.cn/problems/nth-magical-number/
 * 第 N 个神奇数字
 * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
 * 给定三个整数 n , a , b ，返回第 n 个神奇的数字。
 * 因为答案可能很大，所以返回答案 对 1000000007 取模
 */
public class Code03_nthMagicalNumber {

    public static void main(String[] args) {
        int a = 40000, b = 40000;
        int n = 1000000000;
        int i = nthMagicalNumber(n, a, b);
        System.out.println("i = " + i);
    }

    public static int nthMagicalNumber(int n, int a, int b) {
        // 左边界 l 为 0，右边界 r 为 n * min(a, b)，确保包含所有可能的魔法数
        long l = 0, r = (long) n * Math.min(a, b), lcm = lcm(a, b), ans = 0;
        // l = 0
        // r = (long) n * Math.min(a, b)
        // l......r
        while (l <= r) {
            long m = (l + r) / 2;
            // 计算小于等于 m 的能够被 a 或 b 整除的数字个数
            if (m / a + m / b - m / lcm >= n) { // 容斥原理
                // 如果个数大于等于 n，说明第 n 个魔法数在 m 或更小的范围内
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return (int) (ans % 1000000007);
    }

    // 最大公约数
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 最小公倍数
    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
}
